home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Utilities / byacc 1.8.2 / lalr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  11.8 KB  |  718 lines  |  [TEXT/R*ch]
  1. #include "defs.h"
  2.  
  3. typedef struct shorts
  4. {
  5.     struct shorts *next;
  6.     short value;
  7. } shorts;
  8.  
  9. int tokensetsize;
  10. short *lookaheads;
  11. short *LAruleno;
  12. unsigned *LA;
  13. short *accessing_symbol;
  14. core **state_table;
  15. shifts **shift_table;
  16. reductions **reduction_table;
  17. short *goto_map;
  18. short *from_state;
  19. short *to_state;
  20.  
  21. static int infinity;
  22. static int maxrhs;
  23. static int ngotos;
  24. static unsigned *F;
  25. static short **includes;
  26. static shorts **lookback;
  27. static short **R;
  28. static short *INDEX;
  29. static short *VERTICES;
  30. static int top;
  31.  
  32. static void set_state_table _P_((void));
  33. static void set_accessing_symbol _P_((void));
  34. static void set_shift_table _P_((void));
  35. static void set_reduction_table _P_((void));
  36. static void set_maxrhs _P_((void));
  37. static void initialize_LA _P_((void));
  38. static void set_goto_map _P_((void));
  39. static int map_goto _P_((int state, int symbol));
  40. static void initialize_F _P_((void));
  41. static void build_relations _P_((void));
  42. static void add_lookback_edge _P_((int stateno, int ruleno, int gotono));
  43. static short **transpose _P_((short **R, int n));
  44. static void compute_FOLLOWS _P_((void));
  45. static void compute_lookaheads _P_((void));
  46. static void digraph _P_((short **relation));
  47. static void traverse _P_((register int i));
  48.  
  49.  
  50. #if __STDC__
  51. void lalr(void)
  52. #else
  53. void lalr()
  54. #endif
  55. {
  56.     tokensetsize = WORDSIZE(ntokens);
  57.  
  58.     set_state_table();
  59.     set_accessing_symbol();
  60.     set_shift_table();
  61.     set_reduction_table();
  62.     set_maxrhs();
  63.     initialize_LA();
  64.     set_goto_map();
  65.     initialize_F();
  66.     build_relations();
  67.     compute_FOLLOWS();
  68.     compute_lookaheads();
  69. }
  70.  
  71.  
  72.  
  73. #if __STDC__
  74. static void set_state_table(void)
  75. #else
  76. static void set_state_table()
  77. #endif
  78. {
  79.     register core *sp;
  80.  
  81.     state_table = NEW2(nstates, core *);
  82.     for (sp = first_state; sp; sp = sp->next)
  83.     state_table[sp->number] = sp;
  84. }
  85.  
  86.  
  87.  
  88. #if __STDC__
  89. static void set_accessing_symbol(void)
  90. #else
  91. static void set_accessing_symbol()
  92. #endif
  93. {
  94.     register core *sp;
  95.  
  96.     accessing_symbol = NEW2(nstates, short);
  97.     for (sp = first_state; sp; sp = sp->next)
  98.     accessing_symbol[sp->number] = sp->accessing_symbol;
  99. }
  100.  
  101.  
  102.  
  103. #if __STDC__
  104. static void set_shift_table(void)
  105. #else
  106. static void set_shift_table()
  107. #endif
  108. {
  109.     register shifts *sp;
  110.  
  111.     shift_table = NEW2(nstates, shifts *);
  112.     for (sp = first_shift; sp; sp = sp->next)
  113.     shift_table[sp->number] = sp;
  114. }
  115.  
  116.  
  117.  
  118. #if __STDC__
  119. static void set_reduction_table(void)
  120. #else
  121. static void set_reduction_table()
  122. #endif
  123. {
  124.     register reductions *rp;
  125.  
  126.     reduction_table = NEW2(nstates, reductions *);
  127.     for (rp = first_reduction; rp; rp = rp->next)
  128.     reduction_table[rp->number] = rp;
  129. }
  130.  
  131.  
  132.  
  133. #if __STDC__
  134. static void set_maxrhs(void)
  135. #else
  136. static void set_maxrhs()
  137. #endif
  138. {
  139.   register short *itemp;
  140.   register short *item_end;
  141.   register int length;
  142.   register int max;
  143.  
  144.   length = 0;
  145.   max = 0;
  146.   item_end = ritem + nitems;
  147.   for (itemp = ritem; itemp < item_end; itemp++)
  148.     {
  149.       if (*itemp >= 0)
  150.     {
  151.       length++;
  152.     }
  153.       else
  154.     {
  155.       if (length > max) max = length;
  156.       length = 0;
  157.     }
  158.     }
  159.  
  160.   maxrhs = max;
  161. }
  162.  
  163.  
  164.  
  165. #if __STDC__
  166. static void initialize_LA(void)
  167. #else
  168. static void initialize_LA()
  169. #endif
  170. {
  171.   register int i, j, k;
  172.   register reductions *rp;
  173.  
  174.   lookaheads = NEW2(nstates + 1, short);
  175.  
  176.   k = 0;
  177.   for (i = 0; i < nstates; i++)
  178.     {
  179.       lookaheads[i] = k;
  180.       rp = reduction_table[i];
  181.       if (rp)
  182.     k += rp->nreds;
  183.     }
  184.   lookaheads[nstates] = k;
  185.  
  186.   LA = NEW2(k * tokensetsize, unsigned);
  187.   LAruleno = NEW2(k, short);
  188.   lookback = NEW2(k, shorts *);
  189.  
  190.   k = 0;
  191.   for (i = 0; i < nstates; i++)
  192.     {
  193.       rp = reduction_table[i];
  194.       if (rp)
  195.     {
  196.       for (j = 0; j < rp->nreds; j++)
  197.         {
  198.           LAruleno[k] = rp->rules[j];
  199.           k++;
  200.         }
  201.     }
  202.     }
  203. }
  204.  
  205.  
  206. #if __STDC__
  207. static void set_goto_map(void)
  208. #else
  209. static void set_goto_map()
  210. #endif
  211. {
  212.   register shifts *sp;
  213.   register int i;
  214.   register int symbol;
  215.   register int k;
  216.   register short *temp_map;
  217.   register int state2;
  218.   register int state1;
  219.  
  220.   goto_map = NEW2(nvars + 1, short) - ntokens;
  221.   temp_map = NEW2(nvars + 1, short) - ntokens;
  222.  
  223.   ngotos = 0;
  224.   for (sp = first_shift; sp; sp = sp->next)
  225.     {
  226.       for (i = sp->nshifts - 1; i >= 0; i--)
  227.     {
  228.       symbol = accessing_symbol[sp->shift[i]];
  229.  
  230.       if (ISTOKEN(symbol)) break;
  231.  
  232.       if (ngotos == MAXSHORT)
  233.         fatal("too many gotos");
  234.  
  235.       ngotos++;
  236.       goto_map[symbol]++;
  237.     }
  238.     }
  239.  
  240.   k = 0;
  241.   for (i = ntokens; i < nsyms; i++)
  242.     {
  243.       temp_map[i] = k;
  244.       k += goto_map[i];
  245.     }
  246.  
  247.   for (i = ntokens; i < nsyms; i++)
  248.     goto_map[i] = temp_map[i];
  249.  
  250.   goto_map[nsyms] = ngotos;
  251.   temp_map[nsyms] = ngotos;
  252.  
  253.   from_state = NEW2(ngotos, short);
  254.   to_state = NEW2(ngotos, short);
  255.  
  256.   for (sp = first_shift; sp; sp = sp->next)
  257.     {
  258.       state1 = sp->number;
  259.       for (i = sp->nshifts - 1; i >= 0; i--)
  260.     {
  261.       state2 = sp->shift[i];
  262.       symbol = accessing_symbol[state2];
  263.  
  264.       if (ISTOKEN(symbol)) break;
  265.  
  266.       k = temp_map[symbol]++;
  267.       from_state[k] = state1;
  268.       to_state[k] = state2;
  269.     }
  270.     }
  271.  
  272.   FREE(temp_map + ntokens);
  273. }
  274.  
  275.  
  276.  
  277. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  278.  
  279. #if __STDC__
  280. static int map_goto(int state, int symbol)
  281. #else
  282. static int map_goto(state, symbol)
  283. int state;
  284. int symbol;
  285. #endif
  286. {
  287.     register int high;
  288.     register int low;
  289.     register int middle;
  290.     register int s;
  291.  
  292.     low = goto_map[symbol];
  293.     high = goto_map[symbol + 1];
  294.  
  295.     for (;;)
  296.     {
  297.     assert(low <= high);
  298.     middle = (low + high) >> 1;
  299.     s = from_state[middle];
  300.     if (s == state)
  301.         return (middle);
  302.     else if (s < state)
  303.         low = middle + 1;
  304.     else
  305.         high = middle - 1;
  306.     }
  307. }
  308.  
  309.  
  310.  
  311. #if __STDC__
  312. static void initialize_F(void)
  313. #else
  314. static void initialize_F()
  315. #endif
  316. {
  317.   register int i;
  318.   register int j;
  319.   register int k;
  320.   register shifts *sp;
  321.   register short *edge;
  322.   register unsigned *rowp;
  323.   register short *rp;
  324.   register short **reads;
  325.   register int nedges;
  326.   register int stateno;
  327.   register int symbol;
  328.   register int nwords;
  329.  
  330.   nwords = ngotos * tokensetsize;
  331.   F = NEW2(nwords, unsigned);
  332.  
  333.   reads = NEW2(ngotos, short *);
  334.   edge = NEW2(ngotos + 1, short);
  335.   nedges = 0;
  336.  
  337.   rowp = F;
  338.   for (i = 0; i < ngotos; i++)
  339.     {
  340.       stateno = to_state[i];
  341.       sp = shift_table[stateno];
  342.  
  343.       if (sp)
  344.     {
  345.       k = sp->nshifts;
  346.  
  347.       for (j = 0; j < k; j++)
  348.         {
  349.           symbol = accessing_symbol[sp->shift[j]];
  350.           if (ISVAR(symbol))
  351.         break;
  352.           SETBIT(rowp, symbol);
  353.         }
  354.  
  355.       for (; j < k; j++)
  356.         {
  357.           symbol = accessing_symbol[sp->shift[j]];
  358.           if (nullable[symbol])
  359.         edge[nedges++] = map_goto(stateno, symbol);
  360.         }
  361.     
  362.       if (nedges)
  363.         {
  364.           reads[i] = rp = NEW2(nedges + 1, short);
  365.  
  366.           for (j = 0; j < nedges; j++)
  367.         rp[j] = edge[j];
  368.  
  369.           rp[nedges] = -1;
  370.           nedges = 0;
  371.         }
  372.     }
  373.  
  374.       rowp += tokensetsize;
  375.     }
  376.  
  377.   SETBIT(F, 0);
  378.   digraph(reads);
  379.  
  380.   for (i = 0; i < ngotos; i++)
  381.     {
  382.       if (reads[i])
  383.     FREE(reads[i]);
  384.     }
  385.  
  386.   FREE(reads);
  387.   FREE(edge);
  388. }
  389.  
  390.  
  391.  
  392. #if __STDC__
  393. static void build_relations(void)
  394. #else
  395. static void build_relations()
  396. #endif
  397. {
  398.   register int i;
  399.   register int j;
  400.   register int k;
  401.   register short *rulep;
  402.   register short *rp;
  403.   register shifts *sp;
  404.   register int length;
  405.   register int nedges;
  406.   register int done;
  407.   register int state1;
  408.   register int stateno;
  409.   register int symbol1;
  410.   register int symbol2;
  411.   register short *shortp;
  412.   register short *edge;
  413.   register short *states;
  414.   register short **new_includes;
  415.  
  416.   includes = NEW2(ngotos, short *);
  417.   edge = NEW2(ngotos + 1, short);
  418.   states = NEW2(maxrhs + 1, short);
  419.  
  420.   for (i = 0; i < ngotos; i++)
  421.     {
  422.       nedges = 0;
  423.       state1 = from_state[i];
  424.       symbol1 = accessing_symbol[to_state[i]];
  425.  
  426.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  427.     {
  428.       length = 1;
  429.       states[0] = state1;
  430.       stateno = state1;
  431.  
  432.       for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  433.         {
  434.           symbol2 = *rp;
  435.           sp = shift_table[stateno];
  436.           k = sp->nshifts;
  437.  
  438.           for (j = 0; j < k; j++)
  439.         {
  440.           stateno = sp->shift[j];
  441.           if (accessing_symbol[stateno] == symbol2) break;
  442.         }
  443.  
  444.           states[length++] = stateno;
  445.         }
  446.  
  447.       add_lookback_edge(stateno, *rulep, i);
  448.  
  449.       length--;
  450.       done = 0;
  451.       while (!done)
  452.         {
  453.           done = 1;
  454.           rp--;
  455.           if (ISVAR(*rp))
  456.         {
  457.           stateno = states[--length];
  458.           edge[nedges++] = map_goto(stateno, *rp);
  459.           if (nullable[*rp] && length > 0) done = 0;
  460.         }
  461.         }
  462.     }
  463.  
  464.       if (nedges)
  465.     {
  466.       includes[i] = shortp = NEW2(nedges + 1, short);
  467.       for (j = 0; j < nedges; j++)
  468.         shortp[j] = edge[j];
  469.       shortp[nedges] = -1;
  470.     }
  471.     }
  472.  
  473.   new_includes = transpose(includes, ngotos);
  474.  
  475.   for (i = 0; i < ngotos; i++)
  476.     if (includes[i])
  477.       FREE(includes[i]);
  478.  
  479.   FREE(includes);
  480.  
  481.   includes = new_includes;
  482.  
  483.   FREE(edge);
  484.   FREE(states);
  485. }
  486.  
  487.  
  488. #if __STDC__
  489. static void add_lookback_edge(int stateno, int ruleno, int gotono)
  490. #else
  491. static void add_lookback_edge(stateno, ruleno, gotono)
  492. int stateno, ruleno, gotono;
  493. #endif
  494. {
  495.     register int i, k;
  496.     register int found;
  497.     register shorts *sp;
  498.  
  499.     i = lookaheads[stateno];
  500.     k = lookaheads[stateno + 1];
  501.     found = 0;
  502.     while (!found && i < k)
  503.     {
  504.     if (LAruleno[i] == ruleno)
  505.         found = 1;
  506.     else
  507.         ++i;
  508.     }
  509.     assert(found);
  510.  
  511.     sp = NEW(shorts);
  512.     sp->next = lookback[i];
  513.     sp->value = gotono;
  514.     lookback[i] = sp;
  515. }
  516.  
  517.  
  518.  
  519. #if __STDC__
  520. static short **transpose(short **R, int n)
  521. #else
  522. static short **transpose(R, n)
  523. short **R;
  524. int n;
  525. #endif
  526. {
  527.   register short **new_R;
  528.   register short **temp_R;
  529.   register short *nedges;
  530.   register short *sp;
  531.   register int i;
  532.   register int k;
  533.  
  534.   nedges = NEW2(n, short);
  535.  
  536.   for (i = 0; i < n; i++)
  537.     {
  538.       sp = R[i];
  539.       if (sp)
  540.     {
  541.       while (*sp >= 0)
  542.         nedges[*sp++]++;
  543.     }
  544.     }
  545.  
  546.   new_R = NEW2(n, short *);
  547.   temp_R = NEW2(n, short *);
  548.  
  549.   for (i = 0; i < n; i++)
  550.     {
  551.       k = nedges[i];
  552.       if (k > 0)
  553.     {
  554.       sp = NEW2(k + 1, short);
  555.       new_R[i] = sp;
  556.       temp_R[i] = sp;
  557.       sp[k] = -1;
  558.     }
  559.     }
  560.  
  561.   FREE(nedges);
  562.  
  563.   for (i = 0; i < n; i++)
  564.     {
  565.       sp = R[i];
  566.       if (sp)
  567.     {
  568.       while (*sp >= 0)
  569.         *temp_R[*sp++]++ = i;
  570.     }
  571.     }
  572.  
  573.   FREE(temp_R);
  574.  
  575.   return (new_R);
  576. }
  577.  
  578.  
  579.  
  580. #if __STDC__
  581. static void compute_FOLLOWS(void)
  582. #else
  583. static void compute_FOLLOWS()
  584. #endif
  585. {
  586.   digraph(includes);
  587. }
  588.  
  589.  
  590. #if __STDC__
  591. static void compute_lookaheads(void)
  592. #else
  593. static void compute_lookaheads()
  594. #endif
  595. {
  596.   register int i, n;
  597.   register unsigned *fp1, *fp2, *fp3;
  598.   register shorts *sp, *next;
  599.   register unsigned *rowp;
  600.  
  601.   rowp = LA;
  602.   n = lookaheads[nstates];
  603.   for (i = 0; i < n; i++)
  604.     {
  605.       fp3 = rowp + tokensetsize;
  606.       for (sp = lookback[i]; sp; sp = sp->next)
  607.     {
  608.       fp1 = rowp;
  609.       fp2 = F + tokensetsize * sp->value;
  610.       while (fp1 < fp3)
  611.         *fp1++ |= *fp2++;
  612.     }
  613.       rowp = fp3;
  614.     }
  615.  
  616.   for (i = 0; i < n; i++)
  617.     for (sp = lookback[i]; sp; sp = next)
  618.       {
  619.     next = sp->next;
  620.     FREE(sp);
  621.       }
  622.  
  623.   FREE(lookback);
  624.   FREE(F);
  625. }
  626.  
  627.  
  628. #if __STDC__
  629. static void digraph(short **relation)
  630. #else
  631. static void digraph(relation)
  632. short **relation;
  633. #endif
  634. {
  635.   register int i;
  636.  
  637.   infinity = ngotos + 2;
  638.   INDEX = NEW2(ngotos + 1, short);
  639.   VERTICES = NEW2(ngotos + 1, short);
  640.   top = 0;
  641.  
  642.   R = relation;
  643.  
  644.   for (i = 0; i < ngotos; i++)
  645.     INDEX[i] = 0;
  646.  
  647.   for (i = 0; i < ngotos; i++)
  648.     {
  649.       if (INDEX[i] == 0 && R[i])
  650.     traverse(i);
  651.     }
  652.  
  653.   FREE(INDEX);
  654.   FREE(VERTICES);
  655. }
  656.  
  657.  
  658.  
  659. #if __STDC__
  660. static void traverse(int i)
  661. #else
  662. static void traverse(i)
  663. register int i;
  664. #endif
  665. {
  666.   register unsigned *fp1;
  667.   register unsigned *fp2;
  668.   register unsigned *fp3;
  669.   register int j;
  670.   register short *rp;
  671.  
  672.   int height;
  673.   unsigned *base;
  674.  
  675.   VERTICES[++top] = i;
  676.   INDEX[i] = height = top;
  677.  
  678.   base = F + i * tokensetsize;
  679.   fp3 = base + tokensetsize;
  680.  
  681.   rp = R[i];
  682.   if (rp)
  683.     {
  684.       while ((j = *rp++) >= 0)
  685.     {
  686.       if (INDEX[j] == 0)
  687.         traverse(j);
  688.  
  689.       if (INDEX[i] > INDEX[j])
  690.         INDEX[i] = INDEX[j];
  691.  
  692.       fp1 = base;
  693.       fp2 = F + j * tokensetsize;
  694.  
  695.       while (fp1 < fp3)
  696.         *fp1++ |= *fp2++;
  697.     }
  698.     }
  699.  
  700.   if (INDEX[i] == height)
  701.     {
  702.       for (;;)
  703.     {
  704.       j = VERTICES[top--];
  705.       INDEX[j] = infinity;
  706.  
  707.       if (i == j)
  708.         break;
  709.  
  710.       fp1 = base;
  711.       fp2 = F + j * tokensetsize;
  712.  
  713.       while (fp1 < fp3)
  714.         *fp2++ = *fp1++;
  715.     }
  716.     }
  717. }
  718.